public class Main {
    public static void main(String[] args) {

    }
    public class sortTest9 {
        private int[] data;
        public void sort(int[] data){
            this.data = data;
            dfs(0,data.length - 1);
        }

        private void dfs(int start, int end) {
            //分区的时候只有一个元素结束递归
            if (start == end) return;
            //分区(已基准点分区)
            int j = partition(start,end);

            //左分区
            dfs(j - 1, end);
            //右分区
            dfs(start, j + 1);
        }

        private int partition(int start, int end) {
            //定义基准数
            int prev = data[end];
            int less = start;//慢指针
            int great = start;//快指针
            for (; great < end - 1; great++) {
                if (data[great] < prev){
                    //防止无意义的空交换
                    if (great != less) swap(data,less,great);
                    less++;
                }
            }
            //到最后交换基准数(也就是end的值)和慢指针less的值
            swap(data,less,end);

            //慢指针所在的位置就是分区的位置
            return less;
        }

        private void swap(int[] data, int less, int great) {
            int temp = data[less];
            data[less] = data[great];
            data[great] = temp;
        }
    }
}